1629 곱셈

• algorithms

나머지 지수승 관련한 이산수학 교재 캡처 추가. 이 알고리즘이 기반한 원리는 $b^4\mathrm{mod}m$ 이나 $(b^2\mathrm{mod}m)\cdot (b^2\mathrm{mod}m)\mathrm{mod}m$ 이나 같다는 것이다. 주목할 변수는 x일지 몰라도 그 x에 붙일 계수를 알기 위해선 당연하게도 power를 지수승만큼 증가시켜야 한다. 그런데 그냥 $b^1$ $b^2$ $b^3$ ... 이런식이 아닌, $b^{2^1}$ $b^{2^2}$ $b^{2^3}$ 이런 식으로 증가하기 때문에 power를 매 이터레이션마다 제곱을 시키는 것이다.

아래 교재의 예시인 $3^{644}\mathrm{mod}645$를 예로 들면, $644=2^2+2^7+2^9$ 이므로, $3^{6}44\mathrm{mod}645=3^{2^2}\cdot 3^{2^7}\cdot 3^{2^9}\mathrm{mod}645$와 같다. 그래서 x는 i 가 2, 7, 9일때 x = (x * power) mod m을 구하고, power는 매 이터레이션마다 $3^{2^i}$ 를 구하고 있는거고.

source code

"""modular exponentiation 참고: https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/modular-exponentiation"""
from math import ceil, log2


def modular_exponentiation(b: int, exp: int, m: int):
    """나머지 지수승 연산을 수행하는 알고리즘.
    $
    b^{exp} \mod m
    $
    """
    x = 1
    power = b % m
    k = ceil(log2(exp)) + 1 # e의 이진전개의 길이, 1을 더하는 이유는 예외처리 때문이다. 2의 지수승을 e에 넣어보고 풀면 결과가 이상하다. 왜냐하면 아래 for문의 if문을 하나도 통과하지 않기 때문이지.

    for i in range(k):
        if (exp >> i) & 1 == 1:
            # a_i = 1 then,
            x = (x * power) % m
        power = (power * power) % m
    return x


b, exp, m = [int(x) for x in input().split()]

print(modular_exponentiation(b, exp, m))